import java.util.Arrays;

/**
 * 581. 最短无序连续子数组
 */
public class Solution_581 {
    /**
     * 排序
     * <p>
     * 与排序后的数组比较，找到最左边和最右边不匹配的元素即可
     * <p>
     * 时间复杂度：O(nlogn)
     * <p>
     * 空间复杂度：O(n)
     */
    public int findUnsortedSubarray(int[] nums) {
        int[] copyNums = nums.clone();
        Arrays.sort(copyNums);
        int start = copyNums.length, end = 0;
        for (int i = 0; i < copyNums.length; i++) {
            if (copyNums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }

    public static void main(String[] args) {
        Solution_581 solution = new Solution_581();
        int[] nums = { 2, 6, 4, 8, 10, 9, 15 };
        int ans = solution.findUnsortedSubarray(nums);
        System.out.println(ans);
    }
}
